import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2024-01-23
 * Time: 13:04
 * https://www.nowcoder.com/share/jump/7745334641705989076688
 */

public class BM100 {
    // 额定容量
    private final int CAPACITY;
    // 使用 LinkedHashMap 的有序排重特点达到要求
    private final Map<Integer, Integer> map;


    public BM100(int capacity) {
        // 初始化
        CAPACITY = capacity;
        map = new LinkedHashMap<>(CAPACITY);
    }

    public int get(int key) {
        Integer value = map.get(key);
        if (value != null) {// 存在
            // 1. 先删除旧的
            map.remove(key);
            // 2. 再添加回去，同时更新了 key 的位置和 value
            map.put(key, value);
            // 3. 返回结果
            return value;
        } else {// 不存在
            return -1;
        }
    }

    public void set(int key, int value) {
        if (map.size() == CAPACITY) {// 达到最大容量
            if (!map.containsKey(key)) {// 不存在，就删除头
                Integer head = map.keySet().iterator().next();
                map.remove(head);
            } else {// 存在，就删除自身
                map.remove(key);
            }
        } else {// 还有剩余空间，删除自身
            map.remove(key);
        }
        // 添加新的或 key 更新后的 value
        map.put(key, value);
    }
}







class Solution {

    // 1. 封装 Node 记录 key 和 value，就像 HashMap
    static class Node<K, V> {
        // 每个 Node 记录自身的值和前驱后继
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        public Node() {
            this.prev = this.next = null;
        }

        public Node(K key, V value) {
            // 初始化
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
        }
    }

    // 2. 手动实现一个双向链表，用来记录顺序
    static class DoubleLinkedList<K, V> {
        Node<K, V> head;
        Node<K, V> tail;

        public DoubleLinkedList() {
            head = new Node<>();
            tail = new Node<>();
            // 初始时，头尾相连
            head.next = tail;
            tail.prev = head;
        }

        // 尾插
        public void addTail(Node<K, V> node) {
            node.next = tail;
            node.prev = tail.prev;
            node.prev.next = node;
            tail.prev = node;
        }

        // 删除节点
        public void remove(Node<K, V> node) {
            node.next.prev = node.prev;
            node.prev.next = node.next;
            node.next = node.prev = null;
        }

        // 得到头结点
        public Node getHead() {
            return head.next;
        }
    }

    // 3. 实现 LRU

    int CAPACITY;// 额定容量
    Map<Integer, Node<Integer, Integer>> map;// 保证元素去重
    DoubleLinkedList<Integer, Integer> doubleLinkedList;// 保证元素顺序

    public Solution(int capacity) {
        // 初始化
        CAPACITY = capacity;
        map = new HashMap<>();
        doubleLinkedList = new DoubleLinkedList<>();
    }

    public int get(int key) {
        if (map.containsKey(key)) {// 存在
            Node<Integer, Integer> node = map.get(key);
            // 删除后更新位置
            doubleLinkedList.remove(node);
            doubleLinkedList.addTail(node);
            return node.value;
        } else {// 不存在
            return -1;
        }
    }

    public void set(int key, int value) {
        if (map.containsKey(key)) {
            Node<Integer, Integer> node = map.get(key);
            node.value = value;
            map.put(key, node);
            doubleLinkedList.remove(node);
            doubleLinkedList.addTail(node);
        } else {
            if (map.size() == CAPACITY) {
                Node headNode = doubleLinkedList.getHead();
                map.remove(headNode.key);
                doubleLinkedList.remove(headNode);
            }
            Node<Integer, Integer> newNode = new Node<>(key, value);
            map.put(key, newNode);
            doubleLinkedList.addTail(newNode);
        }
    }
}

